REVIEW:


Recursive: Defined in terms of itself

Recursive Algorithm: Calls itself

Rules of Recursion:
(1) One or more base cases
(2) Each recursive call makes progress toward a base case (recursive calls solve smaller version of the original problem)


When to use recursion:

(1) Recursive Data

Folder = File* + Folder*

Family Tree
Family = Father + Mother + Children*, but children have their own families, so
Family = Father + Mother + Family* 

EXAMPLE: [FolderSearch.java]


(2) Divide-and-Conquer
SolveProblem(P)
	if (P is small and can be solved directly)
		Solve P directly
	else
		Divide P into smaller sub-problems p1, p2, ..., pn
		SolveProblem(p1);
		SolveProblem(p2);
		...
		SolveProblem(pn);
		Combine solutions to p1, p2, ..., pn to create a solution for P
	return solution for P

EXAMPLE: [SortExams.txt]


(3) Backtracking Search
	WordSearch, Maze Solver, Boggle

Example: [WordSearch.java]



NEW MATERIAL:

Method Activations
Implementing Recursion with the Runtime Stack
Deep Recursion
Inefficient Recursion



Method Activations

Use FolderSearch.java for activation record examples.

Draw folder hierarchy and describe what order search will process the folders

\
	CS235
		win05
			lectures
		win06
			lectures
		sp07
			lectures
	CS240
		fall06
			lectures
		win07
			lectures
		sp07
			lectures
	CS340
		fall06
			lectures
		win07
			lectures

search(new Folder("\"), "recursion.doc");


search(Folder("\"), "recursion.doc")
    |
    |--> search(Folder("\CS235"), "recursion.doc")
        |
        |--> search(Folder("\CS235\win05"), "recursion.doc")
            |
            |--> search(Folder("\CS235\win05\lectures"), "recursion.doc")

		
Recursion results in multiple, simultaneous activations of the same method

Each activation of a method gets its own copy of the method's parameters and local variables so that different activations don't interfere with each other



Runtime Stack / Activation Records

The parameters and local variables for a method activation are stored in an "Activation Record".

Activation Record Format:

============
Local Vars
------------
Parameters
============


EXAMPLE:

============
subFolder
file
it
------------
name
folder
============


Activation records for all currently active methods are stored on a stack called the "Runtime Stack".

Every time a program calls a method, the currently running method activation is suspended, an activation record is created for the new method activation, and populated with the parameter values and local variables for that method call.

The new activation record is pushed on the top of the runtime stack.

Whenever a method wants to access its parameter values or local variables, it goes to the activation record that is currently on top of the stack.

EXAMPLE


search(new Folder("\"), "taxes.doc");


============
subFolder
file
it
------------
name --------------> "recursion.doc"
folder --------------
============        V
subFolder ---------> Folder("\CS235\win05\lectures")
file
it
------------
name --------------> "recursion.doc"
folder --------------
============        V
subFolder ---------> Folder("\CS235\win05")
file
it
------------
name --------------> "recursion.doc"
folder --------------
============        V
subFolder ---------> Folder("\CS235")
file
it
------------
name   ------------> "recursion.doc"
folder ------------> Folder("\")
============
RUNTIME STACK



Deep Recursion

The runtime stack has a maximum size.  Since each recursive call pushes another activation record on the runtime stack, deep recursion can overflow the runtime stack.

In Java you will get a StackOverflowException

Run Sum.java and see probe the limit on recursion depth

EXAMPLE: Iterating over a list can be done using either a loop or recursion.  If recursion is used, you can easily exceed the maximum recursion depth.

In an editor, demonstrate how recursion can be used to iterate over an ArrayList instead of a loop:

void processList(ArrayList list, int index) {
	if (index < list.size()) {
		Object listElem = list.get(index);
		// process listElem
		processList(list, index + 1);
	}	
}

Recursion that may go arbitrarily deep should be avoided (use loops instead).
[Tail recursion may be handled more efficiently, but this should be verified.]



Inefficient Recursion

The Fibonacci numbers are a sequence of numbers defined by the following formula:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

We would like to implement a method fib(n) that will return the value of the nth Fibonacci number.  This can be done both iteratively and recursively.

Show and explain the code in Fibonacci.java.

Run the code using iterFib and then using recFib.

Why such a big difference in running times?  Computing the nth Fibonacci number only takes (n-1) additions.  Why does the recursive version take so long?

Draw a tree representing the recursive calls that are made to compute fib(5) and show how many redundant recursive calls are made.

This redundancy results in an algorithm that is O(((sqrt(5) + 1) / 2)^n) where the iterative algorithm is O(n).

When using recursion, it is important to avoid such duplication of effort.

One technique for removing the duplication is to store the answer for each recursive call in a table.  Whenever the recursive function is called, the first thing it does is check the table to see if the answer for the current parameter value has already been computed.  If so, it just returns the recorded answer.  If not, it computes the answer and puts it in the table.  This way the same value is never computed twice.